1. Field of the Invention
This invention relates to networks and more particularly relates to buffering of data when routing data in networks.
2. Description of the Related Art
Wireless mesh networks (WMNs) are a type of ad hoc wireless networks that uses multi-hop wireless communications to provide or improve connectivity between mesh routers. The mesh routers may be mobile or stationary. Client devices may connect to their preferred mesh router using wired or wireless technologies. The client traffic is then routed across the mesh from mesh router to mesh router to reach another device within the mesh. Alternatively, the client traffic is routed to an external device accessible via a gateway mesh router that bridges traffic between the WMN and an external network. Client devices may roam between different mesh routers in a network, and as such, their mobility management may be performed as a part of the WMN framework.
The broadcast nature of the shared wireless channel limits the set of wireless nodes that can transmit concurrently. One differentiator between various wireless technologies is the medium access control (MAC) protocol, which controls and coordinates access to the shared wireless spectrum. Distributed wireless nodes often use a carrier sense multiple access with collision avoidance (CSMA/CA) MAC protocol. The IEEE 802.11 family of standards is a popular implementation of CSMA/CA. Wi-Fi radios supporting these standards have become a commodity that may be operated globally in license-exempt frequency bands. The IEEE 802.11 standard also supports ad hoc communication capabilities that may be used to set up WMNs. Amendments under the IEEE 802.11s standard introduce mesh capabilities for multi-hop forwarding at layer two in the network.
A buffer is a temporary storage for information bits. Packet-switched networks implement buffers to accommodate transient traffic bursts. Buffers may prevent packet loss. Buffer sizing is an important network configuration parameter: under-buffered networks lead to frequent packet loss and subsequent under-utilization of network resources, and over-buffered networks lead to increased queuing delays.
Transmission control protocol/internet protocol (TCP/IP) communications are used by a large number of network applications, such as file transfers. TCP provides reliable, in-order delivery of data. TCP uses acknowledgments (ACKs) with retransmissions to provide reliable packet delivery. A sliding window mechanism is provided in TCP for flow control and congestion control. Network capacity information may be determined by adjusting the size of its sliding window (called congestion window). TCP implements an additive increase, multiplicative decrease (AIMD) mechanism to adjust the size of its congestion window in response to network feedback. Thus, TCP operates as a closed-loop feedback system. The TCP congestion control algorithms depend on tight control loops, meaning that there are no substantial queuing delays in the network.
User datagram protocol (UDP) communications are increasingly being used by applications that value timely delivery of data over reliable delivery. These include delay-sensitive applications such as voice over IP (VoIP), gaming, and real-time video broadcast. Usually the application fills in gaps where data is either delayed, lost, or corrupted during its transmission through the network. Thus, minimizing queuing delays is an important performance metric for UDP traffic as the queuing delay contributes to the perceived quality of service (QoS) at the application layer.
A data flow or a data stream is a sequence of data packets (e.g., TCP segments or UDP packets) between two hosts. A flow in IP networks may be identified by a multi-tuple key. One conventional definition of flow uses a 5-tuple key, including source IP address, destination IP address, protocol (e.g., TCP, UDP, ICMP), source port, and destination port. A flow may traverse multiple links (with possibly heterogeneous link capacities) along the path between the source and destination. The end-to-end rate of this flow is limited by the link with the smallest available capacity along this path. That link becomes the bottleneck for this flow.
With declining memory chip prices, system architects may be inclined to over-provision routing buffers. This, however, does not necessarily lead to improved network performance. IP networks, in general, desire to minimize buffering and queuing delays. While this is apparent for real-time flows, it also holds for scenarios where throughput has precedence over delay (e.g., bulk file transfer with TCP). TCP's AIMD rate control algorithm is designed to fill any buffer and invoke an occasional packet loss so as to provide feedback to the sender. Large network buffers increase the delay before this congestion information can be communicated to the TCP source. This may have a number of ramifications: first, it may affect the stability characteristics of the TCP stream, and second, it may impact the delay characteristics for other flows (both real-time and TCP) sharing the buffer with this stream.
A conventional buffer sizing approach used in wired networks is to size the bottleneck link buffers to be greater than the bandwidth delay product (BDP) of the network, such that B≧C×RTT, where B is the bottleneck link buffer, C is the bottleneck link capacity, and RTT is the effective round-trip propagation delay through the bottleneck. BDP represents the maximum carrying capacity of the path between the source and the destination. Because queues in wired networks only build up at bottleneck links, buffer sizing is of minimal concern at other locations in the wired network.
The wireless domain introduces a number of new challenges in understanding the impact of buffer size on network performance. In a wired network, buffer sizing is usually studied by keeping the bottleneck link fully utilized. Wireless links, however, are just an abstraction for shared spectrum between communicating entities and their neighbors, only one of which can successfully transmit at a time. It is not clear how buffers may be associated with a distributed set of nodes, some of which relay traffic for other nodes in the network. Furthermore, the capacity of this shared spectrum is not a known constant, but varies over time due to sporadic noise and interference from other wireless nodes. Finally, for the popular CSMA/CA networks, the packet inter-service time at each transmission hop varies due to the random scheduling by the MAC. This MAC behavior should be accounted for when designing buffer sizing protocols for wireless networks.